Erasure channel is an important channel model. For example, when files are transmitted on the Internet, communications are based on data packets, and usually, each data packet is either received by a receiver without any mistake, or not received by the receiver at all. In the Transmission Control Protocol (TCP for short), an error-check and retransmission mechanism is used against network packet loss, i.e., a feedback channel from an input end to an output end is used to control data packets which need to be retransmitted. The receiver generates a retransmission control signal upon detecting a packet loss, until the complete data packet is received correctly; and the receiver also generates a receiving Acknowledgement (ACK) signal upon receiving a data packet. A sender also traces each data packet until it receives a feedback informing signal, otherwise, the sender starts a retransmission.
The data broadcasting service based on streaming mode and file downloading mode is a point-to-multipoint service, in which no feedback is allowed and the conventional error-check and retransmission mechanism cannot be used, and thus Forward Error Correction (FEC for short) needs to be used to ensure reliable transmission. Typical FECs in the application layer comprises RS codes (Reed-Solomon codes), Fountain codes etc. The RS codes are of high complexity in encoding and decoding, and usually are applicable only in the cases where the code length is small. LT codes (Luby Transform codes) and Raptor codes are two kinds of Fountain codes applicable in practice. The LT codes have linear encoding and decoding time, and thus have substantial improvement compared to the RS codes. The Raptor codes have higher decoding efficiency because of the use of pre-coding technique. The Raptor codes are used as the FEC encoding scheme in Multimedia Broadcast/Multicast Service (MBMS for short) and Digital Video Broadcasting (DVB for short) of 3GPP (3rd Generation Partnership Project).
Low Density Generator matrix Codes (LDGC for short) are linear block codes, and the nonzero elements in the generator matrix thereof are usually sparse. Meanwhile, the LDGC are also systematic codes, and the square matrix composed of the front k columns of the generator matrix thereof is generally an upper triangular or lower triangular matrix, the inversion of which can be computed by iteration method. The encoding of the LDGC is to compute an intermediate variable using the corresponding relation between the information bits and the intermediate variable in the systematic codes, and then, to obtain encoded codewords by multiplying the generator matrix by the intermediate variable. The decoding process of the LDGC is to first compute an intermediate variable using the generator matrix, and then, to compute the information bits using the conversion relation between the information bits and the intermediate variable. The LDGC are much lower than the Raptor codes in encoding complexity, can support the encoding of any information block length and any code rate, and are similar to the Raptor codes in performance which can be close to the theoretical optimal performance.
Compared to the structured Low Density Generator Matrix Codes (LDGC), the LT codes do not support the encoding mode of the systematic codes. Thus, the LT codes can not satisfy some practical FEC encoding requirements. The Raptor codes support the systematic codes, however, the Raptor codes need a separate pre-coding process, i.e., a pre-coding matrix is needed, thus, the encoding complexity is high. The LDGC directly use a generator matrix for encoding, without any additional pre-coding matrix. Moreover, since the backward substitution method is used in the encoding of the LDGC to solve the upper triangular (or lower triangular) formulae, the LDGC are much lower than the Raptor codes in encoding complexity. In a word, compared to the LT codes, the advantage of the LDGC lies in that it supports the systematic codes; and compared to the Raptor codes, the advantage of the LDGC lies in that it has a lower encoding complexity.
Comparing the LDGC codes with the Raptor codes of Fountain company, the encoding complexity of the Raptor codes is relatively high, while there is almost no encoding complexity for the LDGC codes because it is very easy to solve trigonometric formula; since the column weight of the LDGC codes is far lower than that of the Raptor codes, the decoding complexity of the Raptor codes is relatively high while that of the LDGC codes is relatively low; and it should be pointed out that since there is specific density distribution, the matrix density in Gaussian elimination process becomes lower and lower so as to ensure a very low complexity of decoding algorithm; since the physical layer generally can guarantee a low BLER (Block Error Rate), the overhead required is usually not more than 25%, at this time, the LDGC codes can further provide a specially effective decoding algorithm to ensure a far lower decoding complexity than that of Raptor codes; the generating process of encoding and decoding matrix is much easier and faster than that of Raptor codes; the storage of the encoding and decoding matrix is far smaller than that of Raptor codes, for example, in the embodiments of the present invention, only a uniform base matrix of 12*40 is needed to be stored; finally, the LDGC codes are relatively flexible, supporting an arbitrary information group length K and an arbitrary encoding rate r.